// 版权所有2009 Go作者。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

// 包regexp实现正则表达式搜索。
// 
// 接受的正则表达式的语法与
// Perl、Python和其他语言使用的通用语法相同。
// 更准确地说，它是RE2接受的语法，在
// golang.org/s/re2syntax，除了\C.
// 语法概述，run 
// go doc regexp/syntax 
// 
// 此包提供的regexp实现是
// 保证在输入大小上以时间线性方式运行。
// （这是大多数开源
// 正则表达式实现不保证的属性）。有关此属性的更多信息，请参阅
// https:
// 或任何关于自动机理论的书。
// 
// 所有字符都是UTF-8编码的代码点。
// 
// 有16个Regexp方法匹配正则表达式并标识匹配的文本。它们的名称由以下正则表达式匹配：
// 
// 查找（全部）？（字符串）？（子匹配）？（索引）？
// 
// 如果存在“All”，则例程将匹配整个表达式的连续非重叠
// 匹配项。与前面的
// /匹配项相邻的空匹配项将被忽略。返回值是一个切片，其中包含相应非'All'例程的连续
// 返回值。这些例程接受一个额外的整数参数n。如果n>=0，函数最多返回n个
// 匹配/子匹配；否则，它将返回所有这些。
// 
// 如果存在“字符串”，则参数为字符串；否则它是一个字节的片
// ；根据需要调整返回值。
// 
// 如果存在“Submatch”，则返回值是标识表达式的连续子匹配的切片。子匹配是
// 正则表达式中带括号的子表达式（也称为捕获组）的匹配，按打开
// 括号的顺序从左到右编号。子匹配0是整个表达式的匹配，子匹配1 
// 是第一个带括号的子表达式的匹配，依此类推。
// 
// 如果存在“Index”，则匹配项和子匹配项由输入字符串中的字节索引
// 对标识：结果[2*n:2*n+1]标识
// 第n个子匹配项的索引。n==0的对标识整个
// 表达式的匹配项。如果“索引”不存在，则匹配项由匹配项/子匹配项的文本
// 标识。如果索引为负数或文本为零，则表示
// 子表达式与输入中的任何字符串都不匹配。对于'String'版本
// 空字符串表示不匹配或空匹配。
// 
// 还有一部分方法可以应用于从RuneReader读取文本
// 
// 
// MatchReader、FindArderIndex、FindArderSubmatchIndex 
// 
// 这组方法可能会增加。注意，正则表达式匹配可能需要
// 检查匹配返回的文本以外的文本，因此
// 匹配RuneReader中文本的方法可能会在返回之前任意读取输入
// 中的文本。
// 
// （还有一些其他方法与此模式不匹配。）
// 
package regexp

import (
	"bytes"
	"io"
	"regexp/syntax"
	"strconv"
	"strings"
	"sync"
	"unicode"
	"unicode/utf8"
)

// Regexp是已编译正则表达式的表示形式。
// 一个Regexp可以安全地由多个goroutine并发使用，
// 除了配置方法，例如Longest。
type Regexp struct {
	expr           string       // 已传递到编译
	prog           *syntax.Prog // 已编译程序
	onepass        *onePassProg // onepass程序或nil 
	numSubexp      int
	maxBitStateLen int
	subexpNames    []string
	prefix         string         // 未编排中所需的前缀匹配
	prefixBytes    []byte         // 前缀，作为[]字节
	prefixRune     rune           // 前缀中的第一个符文
	prefixEnd      uint32         // 前缀中的最后一个符文pc 
	mpool          int            // 机器池
	matchcap       int            // 记录的匹配长度大小
	prefixComplete bool           // 前缀是整个regexp 
	cond           syntax.EmptyOp // 匹配开始时需要的空宽度条件
	minInputLen    int            // 最小匹配长度输入字节

	// 此字段可通过最长方法
	// 但它是只读的。
	longest bool // regexp是否首选最左最长匹配
}

// 字符串返回用于编译正则表达式的源文本。
func (re *Regexp) String() string {
	return re.expr
}

// Copy返回从re复制的新Regexp对象。
// 在一个副本上调用Longest不会影响另一个副本。
// 
// 已弃用：在早期版本中，在多个goroutine中使用Regexp时，
// 为每个goroutine提供自己的副本有助于避免锁争用。
// 从Go 1.12开始，不再需要使用复制来避免锁争用。
// 如果使用它的原因是为了使
// 具有不同最长设置的两个副本，则复制可能仍然合适。
func (re *Regexp) Copy() *Regexp {
	re2 := *re
	return &re2
}

// Compile解析正则表达式，如果成功，则返回
// 可用于匹配文本的Regexp对象。
// 
// 在与文本进行匹配时，regexp返回一个匹配项，该匹配项
// 在输入中尽早开始（最左侧），并在这些
// 中选择回溯搜索最先找到的匹配项。
// 这个所谓的最左边的第一个匹配与Perl、Python和其他实现使用的语义
// 相同，尽管这个
// 包实现它时不需要回溯。
// 有关POSIX最左最长匹配的信息，请参阅CompilepOfix。
func Compile(expr string) (*Regexp, error) {
	return compile(expr, syntax.Perl, false)
}

// CompilePfix类似于Compile，但将正则表达式
// 限制为POSIX ERE（egrep）语法，并将匹配语义更改为
// 最左最长。
// 
// 也就是说，在与文本进行匹配时，regexp返回一个匹配项，该匹配项
// 在输入端（最左侧）尽早开始，并在这些
// 中选择一个尽可能长的匹配项。
// 这个所谓的最左最长匹配与早期正则表达式实现使用的和POSIX 
// 指定的语义相同。
// 
// 但是，可以有多个最左边最长的匹配，具有不同的
// 子匹配选择，并且此包与POSIX不同。
// 在可能的最左最长匹配中，此包选择
// 回溯搜索将首先找到的匹配，而POSIX 
// 指定选择匹配以最大化第一个
// 子表达式的长度，然后是第二个，从左到右依次类推。
// POSIX规则在计算上是禁止的，甚至没有很好的定义。
// 见https:
func CompilePOSIX(expr string) (*Regexp, error) {
	return compile(expr, syntax.POSIX, true)
}

// 最长使未来的搜索更喜欢最左最长的匹配。
// 也就是说，在与文本进行匹配时，regexp返回一个匹配项，该匹配项
// 在输入端（最左侧）尽早开始，并且在这些
// 中选择一个尽可能长的匹配项。
// 此方法修改Regexp，不能与任何其他方法同时调用
// 。
func (re *Regexp) Longest() {
	re.longest = true
}

func compile(expr string, mode syntax.Flags, longest bool) (*Regexp, error) {
	re, err := syntax.Parse(expr, mode)
	if err != nil {
		return nil, err
	}
	maxCap := re.MaxCap()
	capNames := re.CapNames()

	re = re.Simplify()
	prog, err := syntax.Compile(re)
	if err != nil {
		return nil, err
	}
	matchcap := prog.NumCap
	if matchcap < 2 {
		matchcap = 2
	}
	regexp := &Regexp{
		expr:        expr,
		prog:        prog,
		onepass:     compileOnePass(prog),
		numSubexp:   maxCap,
		subexpNames: capNames,
		cond:        prog.StartCond(),
		longest:     longest,
		matchcap:    matchcap,
		minInputLen: minInputLen(re),
	}
	if regexp.onepass == nil {
		regexp.prefix, regexp.prefixComplete = prog.Prefix()
		regexp.maxBitStateLen = maxBitStateLen(prog)
	} else {
		regexp.prefix, regexp.prefixComplete, regexp.prefixEnd = onePassPrefix(prog)
	}
	if regexp.prefix != "" {
		// TODO（rsc）：通过向包字节添加
		// 索引字符串来删除此分配。
		regexp.prefixBytes = []byte(regexp.prefix)
		regexp.prefixRune, _ = utf8.DecodeRuneInString(regexp.prefix)
	}

	n := len(prog.Inst)
	i := 0
	for matchSize[i] != 0 && matchSize[i] < n {
		i++
	}
	regexp.mpool = i

	return regexp, nil
}

// 在（*Regexp）.doExecute期间使用的*计算机池，
// 按执行队列的大小划分。
// 匹配池[i]机器具有队列大小匹配大小[i]。
// 在64位系统上，每个队列条目为16字节，
// 因此匹配池[0]有16*2*128=4kB的队列，等等。
// 最后的匹配池是非常大的队列的总括。
var (
	matchSize = [...]int{128, 512, 2048, 16384, 0}
	matchPool [len(matchSize)]sync.Pool
)

// get返回用于匹配re的机器。
// 如果可能，它使用re的机器缓存，以避免不必要的分配。
func (re *Regexp) get() *machine {
	m, ok := matchPool[re.mpool].Get().(*machine)
	if !ok {
		m = new(machine)
	}
	m.re = re
	m.p = re.prog
	if cap(m.matchcap) < re.matchcap {
		m.matchcap = make([]int, re.matchcap)
		for _, t := range m.pool {
			t.cap = make([]int, re.matchcap)
		}
	}

	// 如果需要，分配队列。
	// 或重新分配，用于“大型”匹配池。
	n := matchSize[re.mpool]
	if n == 0 { // 大池
		n = len(re.prog.Inst)
	}
	if len(m.q0.sparse) < n {
		m.q0 = queue{make([]uint32, n), make([]entry, 0, n)}
		m.q1 = queue{make([]uint32, n), make([]entry, 0, n)}
	}
	return m
}

// put将机器返回到正确的机器池。
func (re *Regexp) put(m *machine) {
	m.re = nil
	m.p = nil
	m.inputs.clear()
	matchPool[re.mpool].Put(m)
}

// minInputLen遍历regexp以查找任何匹配输入的最小长度
func minInputLen(re *syntax.Regexp) int {
	switch re.Op {
	default:
		return 0
	case syntax.OpAnyChar, syntax.OpAnyCharNotNL, syntax.OpCharClass:
		return 1
	case syntax.OpLiteral:
		l := 0
		for _, r := range re.Rune {
			l += utf8.RuneLen(r)
		}
		return l
	case syntax.OpCapture, syntax.OpPlus:
		return minInputLen(re.Sub[0])
	case syntax.OpRepeat:
		return re.Min * minInputLen(re.Sub[0])
	case syntax.OpConcat:
		l := 0
		for _, sub := range re.Sub {
			l += minInputLen(sub)
		}
		return l
	case syntax.OpAlternate:
		l := minInputLen(re.Sub[0])
		var lnext int
		for _, sub := range re.Sub[1:] {
			lnext = minInputLen(sub)
			if lnext < l {
				l = lnext
			}
		}
		return l
	}
}

// MustCompile与Compile类似，但如果表达式无法解析，则会惊慌失措。
// 它简化了保存已编译正则
// 表达式的全局变量的安全初始化。
func MustCompile(str string) *Regexp {
	regexp, err := Compile(str)
	if err != nil {
		panic(`regexp: Compile(` + quote(str) + `): ` + err.Error())
	}
	return regexp
}

// mustcompilepoix与compilepoix类似，但如果无法解析表达式，则会产生恐慌。
// 它简化了保存已编译正则
// 表达式的全局变量的安全初始化。
func MustCompilePOSIX(str string) *Regexp {
	regexp, err := CompilePOSIX(str)
	if err != nil {
		panic(`regexp: CompilePOSIX(` + quote(str) + `): ` + err.Error())
	}
	return regexp
}

func quote(s string) string {
	if strconv.CanBackquote(s) {
		return "`" + s + "`"
	}
	return strconv.Quote(s)
}

// NumSubexp返回此正则表达式中带括号的子表达式数。
func (re *Regexp) NumSubexp() int {
	return re.numSubexp
}

// SubexpNames返回此正则表达式中带括号的子表达式
// 的名称。第一个子表达式的名称为names[1]，
// 因此，如果m是匹配片段，则m[i]的名称为SubexpNames（）[i]。
// 由于无法命名整个Regexp，因此名称[0]始终为
// 空字符串。不应修改切片。
func (re *Regexp) SubexpNames() []string {
	return re.subexpNames
}

// SubexpIndex返回具有给定名称的第一个子表达式的索引，如果没有具有该名称的子表达式，则返回-1。
// 
// 请注意，可以使用相同的名称编写多个子表达式，如在
// /（？P<bob>a+（？P<bob>b+），其中声明了两个名为“bob”的子表达式。
// 在本例中，SubexpIndex返回正则表达式中最左边的此类子表达式
// 的索引。
func (re *Regexp) SubexpIndex(name string) int {
	if name != "" {
		for i, s := range re.subexpNames {
			if name == s {
				return i
			}
		}
	}
	return -1
}

const endOfText rune = -1

// 输入对输入文本的不同表示形式进行了抽象。它提供
// 一个字符的前瞻。
type input interface {
	step(pos int) (r rune, width int) // 提前一个符文
	canCheckPrefix() bool             // 我们能在不丢失信息的情况下展望未来吗？
	hasPrefix(re *Regexp) bool
	index(re *Regexp, pos int) int
	context(pos int) lazyFlag
}

// inputString扫描字符串。
type inputString struct {
	str string
}

func (i *inputString) step(pos int) (rune, int) {
	if pos < len(i.str) {
		c := i.str[pos]
		if c < utf8.RuneSelf {
			return rune(c), 1
		}
		return utf8.DecodeRuneInString(i.str[pos:])
	}
	return endOfText, 0
}

func (i *inputString) canCheckPrefix() bool {
	return true
}

func (i *inputString) hasPrefix(re *Regexp) bool {
	return strings.HasPrefix(i.str, re.prefix)
}

func (i *inputString) index(re *Regexp, pos int) int {
	return strings.Index(i.str[pos:], re.prefix)
}

func (i *inputString) context(pos int) lazyFlag {
	r1, r2 := endOfText, endOfText
	// 0<pos&&pos<=len（i.str）
	if uint(pos-1) < uint(len(i.str)) {
		r1 = rune(i.str[pos-1])
		if r1 >= utf8.RuneSelf {
			r1, _ = utf8.DecodeLastRuneInString(i.str[:pos])
		}
	}
	// 0<=pos&&pos<len（i.str）
	if uint(pos) < uint(len(i.str)) {
		r2 = rune(i.str[pos])
		if r2 >= utf8.RuneSelf {
			r2, _ = utf8.DecodeRuneInString(i.str[pos:])
		}
	}
	return newLazyFlag(r1, r2)
}

// inputBytes扫描字节片。
type inputBytes struct {
	str []byte
}

func (i *inputBytes) step(pos int) (rune, int) {
	if pos < len(i.str) {
		c := i.str[pos]
		if c < utf8.RuneSelf {
			return rune(c), 1
		}
		return utf8.DecodeRune(i.str[pos:])
	}
	return endOfText, 0
}

func (i *inputBytes) canCheckPrefix() bool {
	return true
}

func (i *inputBytes) hasPrefix(re *Regexp) bool {
	return bytes.HasPrefix(i.str, re.prefixBytes)
}

func (i *inputBytes) index(re *Regexp, pos int) int {
	return bytes.Index(i.str[pos:], re.prefixBytes)
}

func (i *inputBytes) context(pos int) lazyFlag {
	r1, r2 := endOfText, endOfText
	// 0<pos&&pos<=len（i.str）
	if uint(pos-1) < uint(len(i.str)) {
		r1 = rune(i.str[pos-1])
		if r1 >= utf8.RuneSelf {
			r1, _ = utf8.DecodeLastRune(i.str[:pos])
		}
	}
	// 0<=pos&&pos<len（i.str）
	if uint(pos) < uint(len(i.str)) {
		r2 = rune(i.str[pos])
		if r2 >= utf8.RuneSelf {
			r2, _ = utf8.DecodeRune(i.str[pos:])
		}
	}
	return newLazyFlag(r1, r2)
}

// inputReader扫描RuneReader。
type inputReader struct {
	r     io.RuneReader
	atEOT bool
	pos   int
}

func (i *inputReader) step(pos int) (rune, int) {
	if !i.atEOT && pos != i.pos {
		return endOfText, 0

	}
	r, w, err := i.r.ReadRune()
	if err != nil {
		i.atEOT = true
		return endOfText, 0
	}
	i.pos += w
	return r, w
}

func (i *inputReader) canCheckPrefix() bool {
	return false
}

func (i *inputReader) hasPrefix(re *Regexp) bool {
	return false
}

func (i *inputReader) index(re *Regexp, pos int) int {
	return -1
}

func (i *inputReader) context(pos int) lazyFlag {
	return 0 // 未使用
}

// LiteralPrefix返回必须以正则表达式re的任何匹配
// 开头的文字字符串。如果
// 文本字符串包含整个正则表达式，则返回布尔值true。
func (re *Regexp) LiteralPrefix() (prefix string, complete bool) {
	return re.prefix, re.prefixComplete
}

// MatchReader报告RuneReader返回的文本是否包含正则表达式re的任何匹配项。
func (re *Regexp) MatchReader(r io.RuneReader) bool {
	return re.doMatch(r, nil, "")
}

// MatchString报告字符串s 
// 是否包含正则表达式re的任何匹配项。
func (re *Regexp) MatchString(s string) bool {
	return re.doMatch(nil, nil, s)
}

// Match报告字节片b 
// 是否包含正则表达式re的任何匹配项。
func (re *Regexp) Match(b []byte) bool {
	return re.doMatch(nil, b, "")
}

// MatchReader报告RuneReader返回的文本是否包含正则表达式模式的任何匹配项。
// 更复杂的查询需要使用Compile和完整的Regexp接口。
func MatchReader(pattern string, r io.RuneReader) (matched bool, err error) {
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.MatchReader(r), nil
}

// MatchString报告字符串s 
// 是否包含正则表达式模式的任何匹配项。
// 更复杂的查询需要使用Compile和完整的Regexp接口。
func MatchString(pattern string, s string) (matched bool, err error) {
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.MatchString(s), nil
}

// Match报告字节片b 
// 是否包含正则表达式模式的任何匹配项。
// 更复杂的查询需要使用Compile和完整的Regexp接口。
func Match(pattern string, b []byte) (matched bool, err error) {
	re, err := Compile(pattern)
	if err != nil {
		return false, err
	}
	return re.Match(b), nil
}

// ReplaceAllString返回src的副本，用替换字符串repl替换Regexp 
// 的匹配项。在repl中，$符号在Expand中被解释为
// 因此，例如，$1代表第一个子匹配的文本。
func (re *Regexp) ReplaceAllString(src, repl string) string {
	n := 2
	if strings.Contains(repl, "$") {
		n = 2 * (re.numSubexp + 1)
	}
	b := re.replaceAll(nil, src, n, func(dst []byte, match []int) []byte {
		return re.expand(dst, repl, nil, src, match)
	})
	return string(b)
}

// ReplaceAllLiteralString返回src的副本，用替换字符串repl替换Regexp 
// 的匹配项。替换repl直接替换为
// 而不使用Expand。
func (re *Regexp) ReplaceAllLiteralString(src, repl string) string {
	return string(re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
		return append(dst, repl...)
	}))
}

// ReplaceAllStringFunc返回src的副本，其中
// Regexp的所有匹配项都已替换为应用于匹配子字符串的函数repl的返回值
// 。repl返回的替换直接替换为
// 而不使用Expand。
func (re *Regexp) ReplaceAllStringFunc(src string, repl func(string) string) string {
	b := re.replaceAll(nil, src, 2, func(dst []byte, match []int) []byte {
		return append(dst, repl(src[match[0]:match[1]])...)
	})
	return string(b)
}

func (re *Regexp) replaceAll(bsrc []byte, src string, nmatch int, repl func(dst []byte, m []int) []byte) []byte {
	lastMatchEnd := 0 // 最近匹配的结束位置
	searchPos := 0    // 我们下一步查找匹配的位置
	var buf []byte
	var endPos int
	if bsrc != nil {
		endPos = len(bsrc)
	} else {
		endPos = len(src)
	}
	if nmatch > re.prog.NumCap {
		nmatch = re.prog.NumCap
	}

	var dstCap [2]int
	for searchPos <= endPos {
		a := re.doExecute(nil, bsrc, src, searchPos, nmatch, dstCap[:0])
		if len(a) == 0 {
			break // 不再匹配
		}

		// 复制此匹配之前的不匹配字符。
		if bsrc != nil {
			buf = append(buf, bsrc[lastMatchEnd:a[0]]...)
		} else {
			buf = append(buf, src[lastMatchEnd:a[0]]...)
		}

		// 现在插入替换字符串的副本，但不能在另一个匹配后立即插入空字符串的匹配。
		// （否则，我们会对匹配空字符串和非空字符串的模式进行双重替换）；始终至少提前一个字符。
		if a[1] > lastMatchEnd || a[0] == 0 {
			buf = repl(buf, a)
		}
		lastMatchEnd = a[1]

		var width int
		if bsrc != nil {
			_, width = utf8.DecodeRune(bsrc[searchPos:])
		} else {
			_, width = utf8.DecodeRuneInString(src[searchPos:])
		}
		if searchPos+width > a[1] {
			searchPos += width
		} else if searchPos+1 > a[1] {
			// 此子句仅在输入
			// 字符串的末尾需要。在这种情况下，DecodeRuneInstalling返回width=0。
			searchPos++
		} else {
			searchPos = a[1]
		}
	}

	// 在上次匹配后复制不匹配的字符。
	if bsrc != nil {
		buf = append(buf, bsrc[lastMatchEnd:]...)
	} else {
		buf = append(buf, src[lastMatchEnd:]...)
	}

	return buf
}

// ReplaceAll返回src的副本，用替换文本repl替换Regexp 
// 的匹配项。在repl中，$符号在Expand中被解释为
// 因此，例如，$1代表第一个子匹配的文本。
func (re *Regexp) ReplaceAll(src, repl []byte) []byte {
	n := 2
	if bytes.IndexByte(repl, '$') >= 0 {
		n = 2 * (re.numSubexp + 1)
	}
	srepl := ""
	b := re.replaceAll(src, "", n, func(dst []byte, match []int) []byte {
		if len(srepl) != len(repl) {
			srepl = string(repl)
		}
		return re.expand(dst, srepl, src, "", match)
	})
	return b
}

// ReplaceAllLiteral返回src的副本，用替换字节repl替换Regexp 
// 的匹配项。替换的repl直接替换为
// 不使用扩展。
func (re *Regexp) ReplaceAllLiteral(src, repl []byte) []byte {
	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
		return append(dst, repl...)
	})
}

// ReplaceAllFunc返回src的副本，其中
// Regexp的所有匹配项都已替换为应用于匹配字节片的函数repl的返回值。repl返回的替换直接替换为
// 而不使用Expand。
func (re *Regexp) ReplaceAllFunc(src []byte, repl func([]byte) []byte) []byte {
	return re.replaceAll(src, "", 2, func(dst []byte, match []int) []byte {
		return append(dst, repl(src[match[0]:match[1]])...)
	})
}

// func special用于检查字符是否需要转义的位图。
var specialBytes [16]byte

// 特殊报告字节b是否需要通过QuoteMeta转义。
func special(b byte) bool {
	return b < utf8.RuneSelf && specialBytes[b%16]&(1<<(b/16)) != 0
}

func init() {
	for _, b := range []byte(`\.+*?()|[]{}^$`) {
		specialBytes[b%16] |= 1 << (b / 16)
	}
}

// QuoteMeta返回一个字符串，该字符串转义参数文本中的所有正则表达式元字符
// ；返回的字符串是与
// 文本匹配的正则表达式。
func QuoteMeta(s string) string {
	// 字节循环是正确的，因为所有元字符都是ASCII。
	var i int
	for i = 0; i < len(s); i++ {
		if special(s[i]) {
			break
		}
	}
	// 找不到元字符，请返回原始字符串。
	if i >= len(s) {
		return s
	}

	b := make([]byte, 2*len(s)-i)
	copy(b, s[:i])
	j := i
	for ; i < len(s); i++ {
		if special(s[i]) {
			b[j] = '\\'
			j++
		}
		b[j] = s[i]
		j++
	}
	return string(b[:j])
}

// 程序中的捕获值数量可能对应于比regexp中更少的捕获表达式。
// 例如，“（a）{0}”变成一个空程序，因此程序中的最大捕获量为0，但我们需要返回\1的表达式。Pad根据需要在切片a上附加-1。
func (re *Regexp) pad(a []int) []int {
	if a == nil {
		// 不匹配。
		return nil
	}
	n := (1 + re.numSubexp) * 2
	for len(a) < n {
		a = append(a, -1)
	}
	return a
}

// 所有匹配调用最多传递n次
// 在输入文本中包含连续匹配的位置。
// 如果非零，则输入文本为b，否则为s。
func (re *Regexp) allMatches(s string, b []byte, n int, deliver func([]int)) {
	var end int
	if b == nil {
		end = len(s)
	} else {
		end = len(b)
	}

	for pos, i, prevMatchEnd := 0, 0, -1; i < n && pos <= end; {
		matches := re.doExecute(nil, b, s, pos, re.prog.NumCap, nil)
		if len(matches) == 0 {
			break
		}

		accept := true
		if matches[1] == pos {
			// 我们找到了一个空匹配项。
			if matches[0] == prevMatchEnd {
				// 我们不允许在上一个匹配之后出现空匹配，所以忽略它。
				accept = false
			}
			var width int
			// TODO:use step（）
			if b == nil {
				_, width = utf8.DecodeRuneInString(s[pos:end])
			} else {
				_, width = utf8.DecodeRune(b[pos:end])
			}
			if width > 0 {
				pos += width
			} else {
				pos = end + 1
			}
		} else {
			pos = matches[1]
		}
		prevMatchEnd = matches[1]

		if accept {
			deliver(re.pad(matches))
			i++
		}
	}
}

// Find返回一个片段，其中包含正则表达式b中最左侧匹配项的文本。
// 返回值为nil表示不匹配。
func (re *Regexp) Find(b []byte) []byte {
	var dstCap [2]int
	a := re.doExecute(nil, b, "", 0, 2, dstCap[:0])
	if a == nil {
		return nil
	}
	return b[a[0]:a[1]:a[1]]
}

// FindIndex返回一个由两个元素组成的整数切片，用于定义正则表达式b中最左边的匹配项
// 的位置。比赛本身在
// b[loc[0]：loc[1]]。
// 返回值为nil表示不匹配。
func (re *Regexp) FindIndex(b []byte) (loc []int) {
	a := re.doExecute(nil, b, "", 0, 2, nil)
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindString返回一个字符串，该字符串包含常规
// 表达式中s中最左侧匹配项的文本。如果不匹配，则返回值为空字符串
// 但如果正则表达式成功匹配
// 空字符串，则返回值也将为空。如果需要使用FindStringIndex或FindStringSubmatch来区分这些情况，请使用
// 。
func (re *Regexp) FindString(s string) string {
	var dstCap [2]int
	a := re.doExecute(nil, nil, s, 0, 2, dstCap[:0])
	if a == nil {
		return ""
	}
	return s[a[0]:a[1]]
}

// FindStringIndex返回一个由两个元素组成的整数切片，该整数定义了正则表达式最左边的匹配项在s中的位置。匹配
// 本身位于s[loc[0]：loc[1]]。
// 返回值为nil表示不匹配。
func (re *Regexp) FindStringIndex(s string) (loc []int) {
	a := re.doExecute(nil, nil, s, 0, 2, nil)
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindReaderIndex返回一个由两个元素组成的整数切片，用于定义从RuneReader读取的文本中正则表达式最左侧匹配项的位置。在
// 字节偏移量loc[0]到loc[1]-1的输入流中找到匹配文本。
// 返回值为nil表示不匹配。
func (re *Regexp) FindReaderIndex(r io.RuneReader) (loc []int) {
	a := re.doExecute(r, nil, "", 0, 2, nil)
	if a == nil {
		return nil
	}
	return a[0:2]
}

// FindSubmatch返回一个片段，该片段包含b中正则表达式最左侧的
// 匹配项及其
// 子表达式的匹配项（如果有）的文本，如包
// 注释中的“子匹配项”描述所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindSubmatch(b []byte) [][]byte {
	var dstCap [4]int
	a := re.doExecute(nil, b, "", 0, re.prog.NumCap, dstCap[:0])
	if a == nil {
		return nil
	}
	ret := make([][]byte, 1+re.numSubexp)
	for i := range ret {
		if 2*i < len(a) && a[2*i] >= 0 {
			ret[i] = b[a[2*i]:a[2*i+1]:a[2*i+1]]
		}
	}
	return ret
}

// Expand将模板追加到dst并返回结果；在
// 追加过程中，Expand将模板中的变量替换为相应的
// 从src中提取的匹配项。匹配片段应该由
// FindSubmatchIndex返回。
// 
// 在模板中，变量由形式为
// /$name或${name}的子字符串表示，其中name是字母、
// 数字和下划线的非空序列。像$1这样的纯数字名称指的是
// 具有相应索引的子匹配；其他名称指的是
// 捕获用（？P<name>…）语法命名的括号。正则表达式中对超出范围或不匹配索引的引用，或对非
// 的名称的引用将替换为空切片。
// 
// 在$name形式中，名称被视为尽可能长：$1x是
// 相当于${1x}，而不是${1}x，$10相当于${10}，而不是${1}0。
// 
// 要在输出中插入文字$，请在模板中使用$。
func (re *Regexp) Expand(dst []byte, template []byte, src []byte, match []int) []byte {
	return re.expand(dst, string(template), src, "", match)
}

// ExpandString类似于Expand，但模板和源是字符串。
// 它附加并返回一个字节片，以便让调用
// 代码控制分配。
func (re *Regexp) ExpandString(dst []byte, template string, src string, match []int) []byte {
	return re.expand(dst, template, nil, src, match)
}

func (re *Regexp) expand(dst []byte, template string, bsrc []byte, src string, match []int) []byte {
	for len(template) > 0 {
		i := strings.Index(template, "$")
		if i < 0 {
			break
		}
		dst = append(dst, template[:i]...)
		template = template[i:]
		if len(template) > 1 && template[1] == '$' {
			// 将$$视为$。
			dst = append(dst, '$')
			template = template[2:]
			continue
		}
		name, num, rest, ok := extract(template)
		if !ok {
			// 格式不正确；将$视为原始文本。
			dst = append(dst, '$')
			template = template[1:]
			continue
		}
		template = rest
		if num >= 0 {
			if 2*num+1 < len(match) && match[2*num] >= 0 {
				if bsrc != nil {
					dst = append(dst, bsrc[match[2*num]:match[2*num+1]]...)
				} else {
					dst = append(dst, src[match[2*num]:match[2*num+1]]...)
				}
			}
		} else {
			for i, namei := range re.subexpNames {
				if name == namei && 2*i+1 < len(match) && match[2*i] >= 0 {
					if bsrc != nil {
						dst = append(dst, bsrc[match[2*i]:match[2*i+1]]...)
					} else {
						dst = append(dst, src[match[2*i]:match[2*i+1]]...)
					}
					break
				}
			}
		}
	}
	dst = append(dst, template...)
	return dst
}

// extract返回str中前导“$name”或“${name}”中的名称。
// 如果是数字，extract返回设置为该数字的num；否则num=-1。
func extract(str string) (name string, num int, rest string, ok bool) {
	if len(str) < 2 || str[0] != '$' {
		return
	}
	brace := false
	if str[1] == '{' {
		brace = true
		str = str[2:]
	} else {
		str = str[1:]
	}
	i := 0
	for i < len(str) {
		rune, size := utf8.DecodeRuneInString(str[i:])
		if !unicode.IsLetter(rune) && !unicode.IsDigit(rune) && rune != '_' {
			break
		}
		i += size
	}
	if i == 0 {
		// 空名称不正确
		return
	}
	name = str[:i]
	if brace {
		if i >= len(str) || str[i] != '}' {
			// 缺少右大括号
			return
		}
		i++
	}

	// 解析号。
	num = 0
	for i := 0; i < len(name); i++ {
		if name[i] < '0' || '9' < name[i] || num >= 1e8 {
			num = -1
			break
		}
		num = num*10 + int(name[i]) - '0'
	}
	// 不允许前导零。
	if name[0] == '0' && len(name) > 1 {
		num = -1
	}

	rest = str[i:]
	ok = true
	return
}

// FindSubmatchIndex返回一个切片，其中包含标识b中正则表达式最左侧匹配项的索引对，以及由包注释中的“子匹配”和“索引”描述
// 其子表达式的匹配项（如果有）。
// 定义的
// 返回值为nil表示不匹配。
func (re *Regexp) FindSubmatchIndex(b []byte) []int {
	return re.pad(re.doExecute(nil, b, "", 0, re.prog.NumCap, nil))
}

// FindStringsSubmatch返回一段字符串，其中包含s中正则表达式的最左侧匹配项以及
// 其子表达式的匹配项（如果有），如
// 包注释中的“子匹配”描述所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindStringSubmatch(s string) []string {
	var dstCap [4]int
	a := re.doExecute(nil, nil, s, 0, re.prog.NumCap, dstCap[:0])
	if a == nil {
		return nil
	}
	ret := make([]string, 1+re.numSubexp)
	for i := range ret {
		if 2*i < len(a) && a[2*i] >= 0 {
			ret[i] = s[a[2*i]:a[2*i+1]]
		}
	}
	return ret
}

// FindStringsSubmatchIndex返回一个包含索引对的切片
// 标识s中正则表达式的最左侧匹配项，以及
// 与包注释中的“Submatch”和
// “index”描述定义的其子表达式的匹配项（如果有）。
// 返回值为nil表示不匹配。
func (re *Regexp) FindStringSubmatchIndex(s string) []int {
	return re.pad(re.doExecute(nil, nil, s, 0, re.prog.NumCap, nil))
}

// FindReaderSubmatchIndex返回一个包含索引对的切片
// 标识由
// 读取的文本正则表达式的最左侧匹配项及其子表达式的匹配项（如果有），如包注释中的“子匹配”和“索引”描述所定义的
// 。
// 返回值为nil表示不匹配。
func (re *Regexp) FindReaderSubmatchIndex(r io.RuneReader) []int {
	return re.pad(re.doExecute(r, nil, "", 0, re.prog.NumCap, nil))
}

const startSize = 10 // 在“All”例程中开始切片的大小。

// FindAll是Find的“全部”版本；它返回表达式的所有连续
// 匹配项的切片，如
// 包注释中的“all”描述所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAll(b []byte, n int) [][]byte {
	if n < 0 {
		n = len(b) + 1
	}
	var result [][]byte
	re.allMatches("", b, n, func(match []int) {
		if result == nil {
			result = make([][]byte, 0, startSize)
		}
		result = append(result, b[match[0]:match[1]:match[1]])
	})
	return result
}

// FindAllIndex是FindIndex的“全部”版本；它返回表达式的所有
// 连续匹配的一个片段，如包注释中的“all”描述
// 所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllIndex(b []byte, n int) [][]int {
	if n < 0 {
		n = len(b) + 1
	}
	var result [][]int
	re.allMatches("", b, n, func(match []int) {
		if result == nil {
			result = make([][]int, 0, startSize)
		}
		result = append(result, match[0:2])
	})
	return result
}

// FindAllString是FindString的“全部”版本；它返回表达式的所有
// 连续匹配的一个片段，如包注释中的“all”描述
// 所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllString(s string, n int) []string {
	if n < 0 {
		n = len(s) + 1
	}
	var result []string
	re.allMatches(s, nil, n, func(match []int) {
		if result == nil {
			result = make([]string, 0, startSize)
		}
		result = append(result, s[match[0]:match[1]])
	})
	return result
}

// FindAllStringIndex是FindStringIndex的“全部”版本；它返回表达式所有连续匹配项的
// 切片，如包注释中的'all'
// 说明所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllStringIndex(s string, n int) [][]int {
	if n < 0 {
		n = len(s) + 1
	}
	var result [][]int
	re.allMatches(s, nil, n, func(match []int) {
		if result == nil {
			result = make([][]int, 0, startSize)
		}
		result = append(result, match[0:2])
	})
	return result
}

// FindAllSubmatch是FindSubmatch的“全部”版本；它返回表达式所有连续匹配项的片段
// 如包注释中的'all'
// 说明所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllSubmatch(b []byte, n int) [][][]byte {
	if n < 0 {
		n = len(b) + 1
	}
	var result [][][]byte
	re.allMatches("", b, n, func(match []int) {
		if result == nil {
			result = make([][][]byte, 0, startSize)
		}
		slice := make([][]byte, len(match)/2)
		for j := range slice {
			if match[2*j] >= 0 {
				slice[j] = b[match[2*j]:match[2*j+1]:match[2*j+1]]
			}
		}
		result = append(result, slice)
	})
	return result
}

// FindAllSubmatchIndex是FindSubmatchIndex的“全部”版本；它返回
// 表达式所有连续匹配项的一个片段，如包注释中的
// /'all'描述所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllSubmatchIndex(b []byte, n int) [][]int {
	if n < 0 {
		n = len(b) + 1
	}
	var result [][]int
	re.allMatches("", b, n, func(match []int) {
		if result == nil {
			result = make([][]int, 0, startSize)
		}
		result = append(result, match)
	})
	return result
}

// FindAllStringSubmatch是FindStringSubmatch的“全部”版本；它返回表达式的所有连续匹配的片段，如包注释中的“all”描述所定义的。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllStringSubmatch(s string, n int) [][]string {
	if n < 0 {
		n = len(s) + 1
	}
	var result [][]string
	re.allMatches(s, nil, n, func(match []int) {
		if result == nil {
			result = make([][]string, 0, startSize)
		}
		slice := make([]string, len(match)/2)
		for j := range slice {
			if match[2*j] >= 0 {
				slice[j] = s[match[2*j]:match[2*j+1]]
			}
		}
		result = append(result, slice)
	})
	return result
}

// FindAllStringSubmatchIndex是
// FindStringSubmatchIndex的“全部”版本；它返回
// 表达式的所有连续匹配的一个片段，如包
// 注释中的“all”描述所定义。
// 返回值为nil表示不匹配。
func (re *Regexp) FindAllStringSubmatchIndex(s string, n int) [][]int {
	if n < 0 {
		n = len(s) + 1
	}
	var result [][]int
	re.allMatches(s, nil, n, func(match []int) {
		if result == nil {
			result = make([][]int, 0, startSize)
		}
		result = append(result, match)
	})
	return result
}

// 将片段s拆分为由表达式分隔的子字符串，并返回
// 这些表达式之间匹配的子字符串的片段。
// 
// 此方法返回的切片由s 
// 不包含在FindAllString返回的切片中。对不包含元字符的表达式
// 调用时，它等效于strings.SplitN。
// /
// 示例：
// s:=regexp.MustCompile（“a*”）.Split（“abaabaccadaaae”，5）
// /s:[“”，“b”，“b”，“c”，“cadaae”]
// 计数确定返回的子字符串数：
// /n>0:最多n个子字符串；最后一个子字符串将是未拆分的余数。
// n==0:结果为零（零个子字符串）
// n<0:所有子字符串
func (re *Regexp) Split(s string, n int) []string {

	if n == 0 {
		return nil
	}

	if len(re.expr) > 0 && len(s) == 0 {
		return []string{""}
	}

	matches := re.FindAllStringIndex(s, n)
	strings := make([]string, 0, len(matches))

	beg := 0
	end := 0
	for _, match := range matches {
		if n > 0 && len(strings) >= n-1 {
			break
		}

		end = match[0]
		if match[1] != 0 {
			strings = append(strings, s[beg:end])
		}
		beg = match[1]
	}

	if end != len(s) {
		strings = append(strings, s[beg:])
	}

	return strings
}
